// https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/

// 算法思路总结：
// 1. 使用有限状态机处理最多两笔交易问题
// 2. 三个持有状态：第一次持有、第二次持有、第三次持有
// 3. 三个空仓状态：第一次空仓、第二次空仓、第三次空仓
// 4. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    const int INF = 0x3f3f3f3f;
    int maxProfit(vector<int>& prices) 
    {
        int m = prices.size();
        if (m <= 1) return 0;

        int f0 = -prices[0], f1 = -INF, f2 = -INF;
        int g0 = 0, g1 = -INF, g2 = -INF;

        for (int i = 1 ; i < m ; i++)
        {
            int old_f0 = f0, old_f1 = f1, old_f2 = f2;
            int old_g0 = g0, old_g1 = g1, old_g2 = g2;

            f0 = max(old_f0, old_g0 - prices[i]);
            f1 = max(old_f1, old_g1 - prices[i]);
            f2 = max(old_f2, old_g2 - prices[i]);

            g0 = old_g0;
            g1 = max(old_g1, old_f0 + prices[i]);
            g2 = max(old_g2, old_f1 + prices[i]);
        }
        return max({g0, g1, g2});
    }
};

int main()
{
    vector<int> v1 = {3,3,5,0,0,3,1,4}, v2 = {1,2,3,4,5};
    Solution sol;

    cout << sol.maxProfit(v1) << endl;
    cout << sol.maxProfit(v2) << endl;

    return 0;
}